\chapter{绪论}\label{chap:introduction}

本章首先介绍研究背景和最近的图神经网络出现的进展，接着介绍什么是图表征技术和图上的局部特征，最后为全文的行文结构做简单的介绍。

\section{研究背景及意义}
图是一种特殊的数据结构，在数学中，图可以表示成$\mathcal{G}  = <\mathcal{V} ,\mathcal{E} > $,其中$\mathcal{V} ,\mathcal{E} $分别表示顶点集合与边集合，并且边集合$\mathcal{E} $可以是多重集合。而在我们实际应用当中，图往往还可以表示为更加复杂的样子，例如$\mathcal{G}  = <\mathcal{V} ,\mathcal{E} ,\mathcal{W} >$其中$\mathcal{W} $ 表示边的权重集合。

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.6\textwidth]{Img/Moreno_Sociogram_2nd_Grade.png}
    \caption{社交网络}
    \label{fig:SocialGraph}
\end{figure}


图广泛的存在于各种实际生活的应用当中，比如社交网络\ref{fig:SocialGraph}、交通网络\ref{fig:TrafficNetwork}等等。随着大数据时代的到来，如何处理指数级增长的图类型的数据成为研究的难点。而各种基于神经网络的机器学习方法在其他领域取得了令人侧目的成就，这也为神经网络方法引入图领域带来了顺理成章的理由\citep{gnnSurveyZhou}

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.6\textwidth]{Img/trafficNetwork.png}
    \caption{交通网络}
    \label{fig:TrafficNetwork}
\end{figure}

所谓图表征，就是\textbf{将图上的节点或是整个图表征为向量}，也就是目前常常使用的embedding技术，而如何在将具有复杂结构的图数据表征成整齐的向量的同时，仍然保有其图结构的特征，目前仍然是研究的难点。

当我们获得了能够充分表征图的embedding之后，我们就可以将该embedding输入到各种高效的机器学习算法当中去，来做下游的任务，比如图分类，节点分类。

目前embedding的技术常见于当前的SOTA(State Of The Art)模型当中, 由此可见一个好的图表征可以为我们做下游任务带来巨大的提升。


所谓的图的局部结构，也就是一个大图$\mathcal{G} = <\mathcal{V},\mathcal{E}>$中挑选部分节点$\mathcal{V}'$和边$\mathcal{E}'$构成子图，如果选取的边是选出来节点在$\mathcal{E}$中的全部边，称这是诱导出的子图。

在有些图中，我们可以从图的局部结构来判断图的类别，比如社交网络中常常会有中心人物，也就是很多个节点都指向这个节点，如果一个网络中经常出现这样的局部结构我们就可以判断这个网络很可能是社交网络。

最近被提出的模型大都采用端到端的技术，也就是模型自动提取图中的特征，构成embedding，再送入下游任务模型中训练，不需要人为的构造特征。这样的模型是否能够学到图的拓扑信息？还是基于模型复杂的假设空间，用大量的参数强行拟合得到了不错的结果呢？本文就图的局部结构在图分类中的作用进行研究。

\section{国内外研究现状}

2004年，Franco等人提出了第一种基于图的图神经网络(Graph Neural Network,GNN)\citep{firstGNN}模型，从那以后，各种不同的GNN模型相继被提出。

2014年Bruna等人提出基于谱域上图傅里叶变换的图卷积神经网络(Graph Convolution Network,GCN)\citep{GCNFourier},这为后来的图神经网络提供了理论上的依据，同时，由于其存在各种不足，诸如计算效率低，无法局部化等等，也为后来的工作提供了很好的研究方向。

2016年Xavier等人在基于图傅里叶变换上的基础上，对其做近似，提出了基于切比雪夫多项式的ChebyNet\citep{ChebyNet},这在一定程度上实现了图卷积的局部化。

2016年，Kipf和Welling将切比雪夫网络中的多项式限定成一阶，提出了当前最常用的GCN简化模型\citep{1-OrderChebyNet}，这大大提高了GCN做卷积操作的速度，同时也带来了一些局部化的性质。

然而上述基于谱域的方法都需要计算图拉普拉斯矩阵，并对其做特征分解，这在图中加入新节点之后就需要重新训练，不具有良好的泛化性，于是在2017年，Hamilton等人提出基于空域的GraphSAGE\citep{InductiveGCN},这是归纳式学习的图神经网络模型，具有良好的泛化性和比较高的训练速度。

2018年，受到自然语言处理(Natural Language Processing,NLP)领域中广泛被使用的attention机制的启发，Veličković等人提出了图注意力网络(Graph Attetion neTwork,GAT)\citep{GAT}，在许多数据集上表现出良好的性质。随着各种不同的图神经网络模型的提出，也有部分学者受到卷积神经网络(Convolution Neural Network,CNN)中常用的池化机制的启发，提出了一系列的池化方法，比如具有可微性的DIFFPOOL\citep{DiffPool},仿照医学图像处理中常用的UNet设计的GraphUNets\citep{GraphUNets}等等。


\section{研究内容}

本文主要是基于目前常用的图神经网络模型，\textbf{根据图上的一种局部结构属性，来探寻如何能更好地让图神经网络模型结合图的结构属性，并由此来获得更好的embedding}，从而提高下游任务的性能，在本文中，我们的下游任务特指的就是图分类任务，也就是给定一个图，我们预测它所具有的标签。比如给定一个化合物，我们判定它是否对某种疾病有效，这实际上就是一个二分类的问题。

为了结合图的局部特征，我们试图将一种传统的Kernel-based的graphlets kernel中用到的graphlet degree vector(GDV)作为节点属性，并将其引入目前常用于做图分类任务的图神经网络当中去，探究其是否能起到作用，为了防止我们引入GDV这一行为扩大模型的假设空间，我们考虑一种shuffled-GDV来作为对照组，分析得到的结果。


\section{本文结构}

本文共有六个章节，论文结构安排如下：

第一章：主要介绍了课题的研究背景及研究意义，结合国内外研究现状，引出图表征这一任务的困难之处。

第二章：首先介绍了什么是Graphlet——一种图的局部结构，接着介绍了传统的基于kernel的图分类方法，比如随机游走kernel(Random Walk,RW),基于路径的kernel(Path-based),和Graphlet kernel。接着本文介绍了近年流行的图神经网络，比如图卷积神经网络和图注意力网络，还介绍了两种池化的方法diffPool和TopK。

第三章：介绍基于图神经网络如何对图进行图表征，并分析其中存在的不足和可以改进的地方。并且将Graphlet Degree Vector 引入上面提到的模型中，分析其可能发挥的作用，和适用于什么样的数据集。

第四章：实验及结果，并对GDV在所选择数据集上是否具有效用做分析并探究原因。

第五章：对全文内容做总结，并展望未来可能的改进方向。



